//题目:
// 给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
// 回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。
// 并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

// 示例 1：
// 输入：nums = [3,6,9,12]
// 输出：4
// 解释： 
// 整个数组是公差为 3 的等差数列。

// 示例 2：
// 输入：nums = [9,4,7,2,10]
// 输出：3
// 解释：
// 最长的等差子序列是 [4,7,10]。

// 示例 3：
// 输入：nums = [20,1,15,3,10,5,8]
// 输出：4
// 解释：
// 最长的等差子序列是 [20,15,10,5]。
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
public:
    int longestArithSeqLength(vector<int>& nums) 
    {
        //1.创建dp表————dp[i][j]表示：以nums[i]和nums[j]为结尾的，最长等差子序列的长度
        vector<vector<int>> dp(nums.size(),vector<int>(nums.size(),2));
        // vector<int> hash(501,-1);//建立 nums[i]——>i 的映射关系
        unordered_map<int,int> hash;
        //2.初始化
        dp[0][0]=1,hash[nums[0]]=0;
        //3.填表 + 确定返回值
        int ret=2;
        // for(int i=1;i<nums.size();i++)
        // {
        //     for(int j=i-1;j>=0;j--)
        //     {
        //         int k=2*nums[j]-nums[i];
        //         if(k>=0 && hash[k]!=-1 && hash[k]<j)
        //             dp[j][i]=max(dp[j][i],1+dp[hash[k]][j]);
        //         ret=max(ret,dp[i][j]);
        //     }
        //     hash[nums[i]]=i;  
        // }
        for(int i=1;i<nums.size();i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                int k=2*nums[i]-nums[j];
                if(hash.count(k))
                    dp[i][j]=dp[hash[k]][i]+1;
                ret=max(ret,dp[i][j]);
            }
            hash[nums[i]]=i;  
        }
        //4.确定返回值
        return ret;
    }
};